#include <stdio.h>
#include <stdlib.h>
//给你一个整数数组 arr，请你将该数组分隔为长度最多为k的一些(连续)子数组，分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
// 返回将数组分隔变换后能够得到的元素最大和。
// 注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。

/*
先找状态转移方程
发现数组内每一个元素的前面k-1个元素内，一定有一个元素作为该元素所属子数组的首个元素
（不确定是哪个，通过枚举，找到最符合的最大值，就是该元素的状态）
*/
int main(){
    // int k = 3;
    // int arr[] = {1,15,7,9,2,5,10};
    int k = 4;
    int arr[] = {1,4,1,5,7,3,6,1,9,9,3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int *dp = (int*)malloc((n+1)*sizeof(int));
    dp[0] = 0;
    for(int i=1;i<=n;i++){
        int max_sum = 0;
        int max = 0;
        for(int j=i;j>0;j--){
            if(i-j==k){
                break;
            }
            if(arr[j-1]>max){
                max = arr[j-1];
            }
            int sum = dp[j-1] + (i-j+1) * max;
            if(sum>max_sum){
                max_sum = sum;
            }
        }
        dp[i] = max_sum;
    }
    printf("%d",dp[n]);

    return 0;
}
